#include <bits/stdc++.h>

using namespace std;

struct TreeNode 
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

// 递归序的解释
// 用递归实现二叉树的三序遍历
class BinaryTreeTraversalRecursion
{
public:
    // 递归基本样子，用来理解递归序
    void f(TreeNode* head)
    {
        if(head == nullptr) return;
        // 1
        f(head->left);
        // 2
        f(head->right);
        // 3
    }

    // 先序打印所有节点，递归版
    static void preOrder(TreeNode* head)
    {
        if(head == nullptr) return;
        printf("%d ", head->val);
        preOrder(head->left);
        preOrder(head->right);
    }

    // 中序打印所有节点，递归版
    static void inOrder(TreeNode* head)
    {
        if(head == nullptr) return;
        inOrder(head->left);
        printf("%d ", head->val);
        inOrder(head->right);
    }

    // 后序打印所有节点，递归版
    static void posOrder(TreeNode* head)
    {
        if(head == nullptr) return;
        posOrder(head->left);
        posOrder(head->right);
        printf("%d ", head->val);
    }
};

int main()
{
    // 手动构建树
    //       1
    //    2     3
    // 4   5  6   7
    TreeNode* head = new TreeNode(1);
    head->left = new TreeNode(2);
    head->right = new TreeNode(3);
    head->left->left = new TreeNode(4);
    head->left->right = new TreeNode(5);
    head->right->left = new TreeNode(6);
    head->right->right = new TreeNode(7);
    
    printf("先序遍历递归版\n");
    BinaryTreeTraversalRecursion::preOrder(head);
    printf("\n");

    printf("中序遍历递归版\n");
    BinaryTreeTraversalRecursion::inOrder(head);
    printf("\n");

    printf("后序遍历递归版\n");
    BinaryTreeTraversalRecursion::posOrder(head);
    printf("\n");

    return 0;
}